package java学习.代码随想录.动态规划;

import java.util.Arrays;

/**
 * **************
 * 项目名称: 蓝桥杯-Java学习 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦Lenovo <br/>
 * 创建时间: 2022/9/2 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class 买卖股票的最佳时机 {
    /**
     * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
     * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
     * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
     * 链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock
     */

    /**
     * 1. dp[i] : 前 i 天 (第i天卖出 ) 的获取最大利润。
     * 2. 分为 在当天 卖出 还是 不卖出。 取最大值
     *  不卖出： dp[i-1]
     *  卖出：   当天入手的价格 -  已知的 历史最低价格
     *  主要还是 通过例子推出的公式： dp[i] = max(dp[i-1],prices[i]- min(prices[0~i-1]))
     * 3. 初始化：dp[0] = 0; 确保dp利润最低是0, 因为 卖出的 结果可能是负数
     */
    public static int maxProfit(int[] prices) {

        int n = prices.length;
        int[] dp = new int[n];
        int min = prices[0];
//        dp[i] = max(dp[i-1],prices[i]- min)
//        min = 0 ~ i-1 prices 的 最小值
//        从1 开始是因为需要dp[i-1];
        for (int i = 1; i <n; i++) {
            min = Math.min(prices[i],min);
            dp[i] = Math.max(dp[i-1],prices[i]- min);

        }
        System.out.println(Arrays.toString(dp));
        return  dp[n-1];
    }


    public static void main(String[] args) {

//        输入：[7,1,5,3,6,4]
//        输出：5
        int []test = {7,1,5,3,6,4};
        System.out.println(maxProfit(test));

    }
}
